#include<bits/stdc++.h>
#define int long long
#define re register
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
#ifdef ONLINE_JUDGE
char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
template<typename T> inline int read(T &num){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return num=f?-x:x;
}
inline int Read()
{
	re int x=0,f=0;re char ch=getchar();
	while(!isdigit(ch)) f|=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
template<typename T> inline void write(T num)
{
	num=num<0?putchar('-'),-num:num;
	num>9?write(num/10),0:0;
	putchar(num%10+48);
}
template<typename T> inline void writeln(T num)
{
	write(num);
	putchar('\n');
}
///////////////////////////////////////////////////////////////
vector<int> graph[1001];
int n,a[501],x,y,ans;
int per[501],cal[501];
mt19937 rnd(1145141919);
signed main()
{
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	read(n);
	iota(per+1,per+n+1,1);
	rep(i,1,n) read(a[i]);
	rep(i,1,n-1) read(x),read(y),graph[x].emplace_back(y),graph[y].emplace_back(x);
	if(n<=10)
	{
		do
		{
			memcpy(cal,a,sizeof cal);
			int res=0;
			rep(i,1,n)
			{
				res+=cal[per[i]];
				for(int j:graph[per[i]])cal[j]+=cal[per[i]];
			}
			ans=max(ans,res);
		} while(next_permutation(per+1,per+n+1));
		writeln(ans);
		return 0;
	}
	while(clock()*1.0/CLOCKS_PER_SEC<.9)
	{
		shuffle(per+1,per+n+1,rnd);
		memcpy(cal,a,sizeof cal);
		int res=0;
		rep(i,1,n)
		{
			res+=cal[per[i]];
			for(int j:graph[per[i]])cal[j]+=cal[per[i]];
		}
		ans=max(ans,res);
	}
	writeln(ans);
    return 0;
}
// 20pts
